﻿#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)

//递归和非递归分别实现求第n个斐波那契数

#include <stdio.h>
//递归
int Fib1(int n)
{
	if (n == 1)
		return 1;
	if (n == 2)
		return 1;
	return Fib1(n - 1) + Fib1(n - 2);
}
//非递归
int Fib2(int n)
{
	int i = 0;
	int a = 1;
	int b = 1;
	int c = 0;
	if (n <= 2)
		return 1;
	for (i = 0; i < n-2; i++)
	{
		c = a + b;
		b = a;
		a = c;
	}
	return c;
}

int main()
{
	int n = 0;
	int ret1 = 0;
	int ret2 = 0;
	scanf("%d", &n);

	ret1 = Fib1(n);
	ret2 = Fib2(n);

	printf("%d\n%d\n", ret1, ret2);

	return 0;
}